import java.util.*;

/**
 * 题目：小明找位置
 * 
 * 题目描述：
 * 小朋友出操，按学号从小到大排成一列；小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。
 * 算法复杂度要求不高于nLog(n)；学号为整数类型，队列规模<=10000。
 * 
 * 输入描述：
 * 1. 第一行：输入已排成队列的小朋友的学号（正整数），以","隔开；
 *    例如：93 95 97 100 102 123 155
 * 2. 第二行：小明学号，如110；
 * 
 * 输出描述：
 * 输出一个数字，代表队列位置（从1开始）。
 * 例如：6
 * 
 * 示例1：
 * 输入：
 * 93 95 97 100 102 123 155
 * 110
 * 输出：
 * 6
 * 
 * 解题思路：
 * 这是一个在有序数组中查找插入位置的问题，可以使用二分查找算法，时间复杂度为O(log n)，满足题目要求。
 * 
 * 算法分析：
 * - 时间复杂度：O(log n)
 * - 空间复杂度：O(1)
 * - 算法类型：二分查找
 */
public class XiaoMingFindPosition {
    
    /**
     * 方法1：标准二分查找（推荐使用）
     * 在有序数组中查找插入位置
     * 
     * 算法思路：
     * 1. 使用二分查找在有序数组中找到小明学号的插入位置
     * 2. 如果找到相同学号，返回该位置
     * 3. 如果没找到，返回应该插入的位置
     * 
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     */
    public static int findPosition1(int[] students, int xiaoMingId) {
        int left = 0, right = students.length;
        while (left < right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (students[mid] < xiaoMingId) {
                left = mid + 1; // 小明学号在右半部分
            } else {
                right = mid; // 小明学号在左半部分或当前位置
            }
        }
        return left + 1; // 位置从1开始计数
    }
    
    /**
     * 方法2：递归二分查找
     * 使用递归实现二分查找
     * 
     * 算法思路：
     * 1. 递归地将搜索范围缩小一半
     * 2. 根据中间元素与目标值的关系决定搜索左半部分还是右半部分
     * 3. 递归终止条件：搜索范围为空
     * 
     * 时间复杂度：O(log n)
     * 空间复杂度：O(log n) - 递归调用栈
     */
    public static int findPosition2(int[] students, int xiaoMingId) {
        return binarySearchRecursive(students, xiaoMingId, 0, students.length) + 1;
    }
    
    /**
     * 递归二分查找的辅助方法
     * @param arr 有序数组
     * @param target 目标值（小明学号）
     * @param left 左边界
     * @param right 右边界
     * @return 插入位置
     */
    private static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left >= right) return left; // 递归终止条件
        int mid = left + (right - left) / 2; // 计算中间位置
        if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right); // 搜索右半部分
        } else {
            return binarySearchRecursive(arr, target, left, mid); // 搜索左半部分
        }
    }
    
    /**
     * 方法3：使用Arrays.binarySearch（Java内置方法）
     * 利用Java内置的二分查找方法
     * 
     * 算法思路：
     * 1. 使用Arrays.binarySearch进行二分查找
     * 2. 如果返回值>=0，说明找到了，直接返回位置
     * 3. 如果返回值<0，说明没找到，-(返回值+1)就是插入位置
     * 
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     */
    public static int findPosition3(int[] students, int xiaoMingId) {
        int index = Arrays.binarySearch(students, xiaoMingId);
        if (index < 0) {
            index = -(index + 1); // 转换为插入位置
        }
        return index + 1; // 位置从1开始计数
    }
    
    /**
     * 方法4：线性查找（备选方案）
     * 虽然时间复杂度为O(n)，但在小数据量下可能更快
     * 
     * 算法思路：
     * 1. 从数组开头开始遍历
     * 2. 找到第一个大于等于小明学号的位置
     * 3. 返回该位置（从1开始计数）
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 适用场景：数据量很小（<100）时可能比二分查找更快
     */
    public static int findPosition4(int[] students, int xiaoMingId) {
        for (int i = 0; i < students.length; i++) {
            if (students[i] >= xiaoMingId) {
                return i + 1; // 找到第一个大于等于小明学号的位置
            }
        }
        return students.length + 1; // 如果所有学号都小于小明学号，排在最后
    }
    
    /**
     * 方法5：使用TreeSet（高级数据结构）
     * 利用TreeSet的有序特性和红黑树实现
     * 
     * 算法思路：
     * 1. 将所有学号存入TreeSet（自动排序）
     * 2. 使用headSet方法获取小于小明学号的所有元素
     * 3. headSet的大小就是小明应该插入的位置
     * 
     * 时间复杂度：O(n log n) - 构建TreeSet
     * 空间复杂度：O(n) - TreeSet存储
     * 适用场景：需要频繁查询插入位置的场景
     */
    public static int findPosition5(int[] students, int xiaoMingId) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int id : students) {
            treeSet.add(id); // 自动去重并排序
        }
        return treeSet.headSet(xiaoMingId).size() + 1; // 小于小明学号的元素个数+1
    }
    
    /**
     * 主方法 - 程序入口
     * 用于测试所有算法实现
     * 
     * 输入格式：
     * 第一行：已排队的学号，用空格分隔
     * 第二行：小明学号
     * 
     * 输出格式：
     * 显示所有5种方法的结果
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取已排队的学号
        System.out.println("请输入已排队的学号（用空格分隔）：");
        String[] studentIds = scanner.nextLine().split(" ");
        int[] students = new int[studentIds.length];
        for (int i = 0; i < studentIds.length; i++) {
            students[i] = Integer.parseInt(studentIds[i]);
        }
        
        // 读取小明学号
        System.out.println("请输入小明学号：");
        int xiaoMingId = scanner.nextInt();
        
        // 测试所有方法并输出结果
        System.out.println("\n=== 所有算法结果对比 ===");
        System.out.println("方法1（标准二分查找）: " + findPosition1(students, xiaoMingId));
        System.out.println("方法2（递归二分查找）: " + findPosition2(students, xiaoMingId));
        System.out.println("方法3（Arrays.binarySearch）: " + findPosition3(students, xiaoMingId));
        System.out.println("方法4（线性查找）: " + findPosition4(students, xiaoMingId));
        System.out.println("方法5（TreeSet）: " + findPosition5(students, xiaoMingId));
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（标准二分查找），时间复杂度最优：O(log n)");
        
        scanner.close();
    }
}
